#!/usr/bin/python
# Filename: Heap.py

# Min-Heap and Max-Heap, with sequential solution
# Heap is also a solution of priority queue.


class MinHeap:
    '''Sequential Min-Heap'''
    def __init__(self):
        self.items = []
        self.size = 0

    def __str__(self):
        start = 0
        length = 1
        string = ""
        while start < len(self.items):
            string += "\n"
            string += str(self.items[start:start+length])
            start += length
            length *= 2
        return string

    def build_heap(self, l):
        # 1/2 nodes(leafs) need not move
        # 1/4 nodes(leafs' parents) need move at most 1 step
        # 1/8 nodes ... 2 step
        # so total move cost time O(n)
        # sift_up or sift_down cost time O(log(n))
        self.items = l[:]
        self.size = len(l)
        # ((self.size-1)-1)/2 is tha last parent
        for i in range(self.size/2-1, -1, -1):
            self.sift_down(i)

    def is_leaf(self, pos):
        return pos < self.size and pos >= self.size/2

    def left_child(self, pos):
        if pos < 0: return -1
        if 2*pos+1 < self.size: return 2*pos+1
        else: return -1

    def right_child(self, pos):
        if pos < 0: return -1
        if 2*(pos+1) < self.size: return 2*(pos+1)
        else: return -1

    def parent(self, pos):
        if pos <= 0 or pos >= self.size: return -1
        else: return (pos-1)/2

    def remove(self, pos):
        if pos < 0 or pos > self.size-1: return None
        val = self.items[pos]
        self.items[pos] = self.items[self.size-1]
        self.items.pop()
        self.size -= 1
        if self.size > 1:
            # caution: sift_up then sift down,
            # bcz last items may be a smaller one
            self.sift_up(val)
            self.sift_down(val)
        return val

    def insert(self, value):
        self.items.append(value)
        self.size += 1
        self.sift_up(self.size-1)

    def remove_min(self):
        if self.size == 0: return None
        val = self.items[0]
        self.items[0] = self.items[self.size-1]
        self.items.pop()
        self.size -= 1
        if self.size > 1:
            self.sift_down(0)
        return val

    def min(self):
        if self.size == 0: return None
        else: return self.items[0]

    def set_root(self, value):
        if self.size == 0:
            self.items.append(value)
            self.size += 1
        else:
            self.items[0] = value
            self.sift_down(0)

    def sift_up(self, pos):
        i = pos
        j = (pos-1)/2
        temp = self.items[i]
        while j >= 0:
            if temp < self.items[j]:
                self.items[i] = self.items[j]
                i = j
                j = (j-1)/2
            else: break
        self.items[i] = temp

        # this one is shorter
        #i = pos
        #temp = self.items[i]
        #while i > 0 and self.items[self.parent(i)] > temp:
        #    self.items[i] = self.items[self.parent(i)]
        #    i = self.parent(i)
        #self.items[i] = temp

    def sift_down(self, pos):
        # it's an internal operation, pos can be see as valid
        i = pos
        j = 2*pos+1
        temp = self.items[i]
        while j < self.size:
            if j < self.size - 1 and self.items[j] > self.items[j+1]:
                j = j+1
            if temp > self.items[j]:
                self.items[i] = self.items[j]
                i = j
                j = 2*j+1
            else: break
        self.items[i] = temp


class MaxHeap:
    '''Sequential Max-Heap'''
    pass

if __name__ == "__main__":

    def test_of_min_heap():
        min_heap = MinHeap()
        l = [3, 1, 4, 2, 5, 7, 6, 9, 4, 8]
        min_heap.build_heap(l)
        print "min_heap.build_heap(l):", min_heap
        min_heap.insert(2)
        print "min_heap.insert(2):", min_heap
        print "min_heap.remove_min():", min_heap.remove_min(), min_heap
        print "min_heap.remove(5):", min_heap.remove(5), min_heap
        min_heap.set_root(10)
        print "min_heap.set_root(10):", min_heap

    test_of_min_heap()
